#include<bits/stdc++.h>
using namespace std;
struct node{
    int Front;
    int Back;
    int val;
};
bool cmp(node t1,node t2){
    return t1.Front<t2.Front;
}
int t;
int main(){
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    cin>>t;
    while(t--){
        node Pr[100005],vis[200005];
        bool used[100005];
        memset(used,false,sizeof(used));
        int a[200005],cnt=0,tot,ans=0;
        for(int i=1;i<=200003;i++)vis[i].val=0;
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            vis[i].Front=-1;
            if(!vis[a[i]].val){
                vis[a[i]].val=1;
                Pr[++cnt].Front=i;
                Pr[cnt].val=a[i];
                vis[i].Front=cnt;
                vis[a[i]].Back=cnt;
            }
            else if(vis[a[i]].val==1){
                vis[a[i]].val=2;
                vis[i].Front=cnt;
                Pr[vis[a[i]].Back].Back=i;
            }
        }
        tot=cnt;
        for(int i=1;i<=cnt;i++)
            if(!Pr[i].Back||vis[Pr[i].Front].val!=2){
                Pr[i].Front=Pr[i].Back=Pr[i].val=0;
                tot--;
            }
        while(tot){
            for(int i=1;i<=cnt;i++){
                if(used[i])continue;
                int cur=0,St=Pr[i].Front,En=Pr[i].Back;
                for(int j=St+1;j<En;j++){
                    if(vis[j].Front!=0&&Pr[vis[j].Front].Back>En){
                        cur+=Pr[vis[j].Front].val;
                    }
                }
                if(cur<=Pr[i].val){
                    tot--;
                    ans+=Pr[i].val;
                    vis[Pr[i].Front].Front=vis[Pr[i].Front].Front=0;
                    used[i]=true;
                    for(int j=St+1;j<En;j++){
                        if(vis[vis[j].Front].Back!=-3&&vis[j].Front!=0&&Pr[vis[j].Front].Back>En){
                            tot--;
                            vis[vis[j].Front].Back=-3;
                        }
                    }
                }
            }
        }
        tot=cnt;
        while(tot){
            for(int i=1;i<=cnt;i++){
                if(used[i])continue;
                int cur=0,St=Pr[i].Front,En=Pr[i].Back;
                for(int j=St+1;j<En;j++){
                    if(vis[j].Front!=0&&Pr[vis[j].Front].Back>En){
                        cur+=Pr[vis[j].Front].val;
                    }
                }
                if(cur<=Pr[i].val){
                    tot--;
                    ans+=Pr[i].val;
                    vis[Pr[i].Front].Front=vis[Pr[i].Back].Front=0;
                    used[i]=true;
                    for(int j=St+1;j<En;j++){
                        if(!used[vis[j].Front]&&vis[j].Front!=0&&Pr[vis[j].Front].Back>En){
                            tot--;
                            vis[Pr[i].Front].Front=vis[Pr[i].Back].Front=0;
                        }
                    }
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}
